package base;

import static base.Edge.NOT_TURN_ON;
import static base.Edge.TURN_OFF;
import static base.Edge.TURN_ON;
import static com.google.common.base.Predicates.not;
import static com.google.common.collect.Iterables.concat;
import static com.google.common.collect.Iterables.filter;
import static com.google.common.collect.Iterables.transform;
import static com.google.common.collect.Sets.difference;
import static com.google.common.collect.Sets.intersection;
import static java.util.Collections.disjoint;

import java.util.Collection;
import java.util.Collections;
import java.util.Iterator;
import java.util.List;
import java.util.Set;
import java.util.SortedMap;
import java.util.SortedSet;
import java.util.Map.Entry;

import base.InvertVertexBuilder.InvertVertex;
import collect.Predicates;

import com.google.common.base.Function;
import com.google.common.base.Predicate;
import com.google.common.collect.HashMultimap;
import com.google.common.collect.HashMultiset;
import com.google.common.collect.ImmutableList;
import com.google.common.collect.ImmutableSet;
import com.google.common.collect.ImmutableSortedSet;
import com.google.common.collect.Iterables;
import com.google.common.collect.Iterators;
import com.google.common.collect.Lists;
import com.google.common.collect.Maps;
import com.google.common.collect.Multiset;
import com.google.common.collect.SetMultimap;
import com.google.common.collect.Sets;
import com.google.common.collect.SortedSetMultimap;
import com.google.common.collect.TreeMultimap;

public class InverterUtils {

	/**
	 * Remove all the terms that are known to be true, by way of either overlapping with {@code fixed}
	 * or being a super-set of another term.
	 * @param terms the unreduced terms
	 * @param fixed the known true variables
	 * @return the {@code terms} object, with any super-set term removed.
	 * No individual term is mutated, only the contents of {@code terms}.
	 * @throws NullPointerException guaranteed to throw a {@link NullPointerException} if either {@code terms} or
	 * {@code fixed} is {@code null}.
	 */
	public static SortedSet<SortedSet<Integer>> reduceTerms(
		@Modified	final SortedSet<SortedSet<Integer>> terms,
		//in J7 - @Modified SortedSet<@Unmodified SortedSet<Integer>> terms
		@Unmodified	final Set<Integer> fixed)
		throws NullPointerException
	{
		if (terms.isEmpty()) return terms; //nothing to do
		//TODO: http://www.springerlink.com/content/vgq5211j2222664r/ - improve superset removal?
		
		/*
		 * algorithm:
		 * need to iterate over terms and remove the ones that are super-sets
		 * in order to use built-in iterator idiom, need to have a duplicate to reference
		 * 1 - construct duplicate, excluding terms that match fixed content;
		 * 1a, since immutableset has consistent order relative to its source construction, and the source
		 * is in the proper sort order, not necessary to make a sorted set
		 * 1b - can also remove terms that intersect fixed
		 * 2 - iterate over the copy, removing all possible super-sets; only need to consult the tail-set
		 * with greater size than the term from the copy, and only when the term hasn't already been
		 * removed (since it's super-sets will also have already been removed).
		 */
		
		final ImmutableSet.Builder<Set<Integer>> copyBuilder = ImmutableSet.builder();

		if (fixed.isEmpty()) { copyBuilder.addAll(terms); }
		else { //might need to remove some terms, do this while building copy
			final Iterator<SortedSet<Integer>> iter = terms.iterator();
			while (iter.hasNext()) {
				Set<Integer> holder = iter.next();
				if ( !disjoint(holder, fixed) ) { iter.remove(); }
				else { copyBuilder.add(holder); }
			}
			
			if (terms.isEmpty()) return terms; //if everything goes away, done - saves construction of copy
		}
		
		for (final Set<Integer> possibleSubSet : copyBuilder.build() )
			if (terms.isEmpty() || possibleSubSet.size() == terms.last().size()) {
				return terms;
			} else if (terms.contains(possibleSubSet)) {
				final Iterator<SortedSet<Integer>> iter = terms.tailSet(SmallestFirst.markerSet(possibleSubSet.size())).iterator();
				while (iter.hasNext())
					if (iter.next().containsAll(possibleSubSet)) iter.remove();
			};
		
		return terms;
	}

	/**
	 * Creates a {@link Predicate} for testing if a {@link Set} of integers intersects fixed,
	 * or is a super-set of some other term in {@code terms).
	 * @param fixed the fixed set
	 * @param terms the set of terms
	 * @return p(input) = !disjoint(input,fixed) || sum_terms(term in input)
	 * The resulting predicate will also throw a {@link NullPointerException} for {@code input == null}.
	 */
	public static Predicate<Set<Integer>> termPredicate(
		@Unmodified final Set<Integer> fixed, 
		@Unmodified final SortedSet<SortedSet<Integer>> terms) {
		return new Predicate<Set<Integer>>(){
			@Override public boolean apply(final Set<Integer> input) {
				if 	( !Collections.disjoint(fixed, input) ) return true;

				for ( SortedSet<Integer> term : terms.headSet(SmallestFirst.markerSet(input.size())) )
					if (input.containsAll(term)) return true;

				return false;
			}
		};
	}
	
	/**
	 * Processes the onPrecursors to finalize knownRBar; also opportunistically builds knownG and gTerms.
	 * This is only initial pruning; knownG and gTerms will still have to be finalized after knownGBar
	 * is finalized.
	 * <p>
	 * Returns false iff the onPrecursors are inconsistent with known information - i.e., an onPrecursor
	 * state hits a knownR, or knownGBar contains all of some onPrecursor state.
	 * @param onPrecursors the sets of vertices that are on before this vertex is on
	 * @param knownR known inhibiting edges
	 * @param knownGBar known non-activating edges
	 * @param knownRBar known non-inhibiting edges
	 * @param knownG known activating edges
	 * @param gTerms the sorted set of sets of vertices that are on before before this vertex is on
	 * @return an empty set if there are no conflicts, otherwise a map of knownR or knownGBar 
	 * that cause problems
	 */
	public static SetMultimap<Edge,Integer> processOnPrecursors(
			@Unmodified final Set<Integer> knownR, 
			@Unmodified final Set<Integer> knownGBar,
			@Modified	final Set<Integer> knownRBar,
			@Modified	final Set<Integer> knownG,
			@Modified	final SortedSet<SortedSet<Integer>> gTerms,
			@Unmodified	final Iterable<? extends Set<Integer>> onPrecursors)
	{
		SetMultimap<Edge,Integer> conflicts = HashMultimap.create();
		for (Set<Integer> term : Iterables.transform(onPrecursors, gTermTransform(knownR,knownGBar,knownRBar,conflicts)))
			inject(term, gTerms, knownG);
		return conflicts;
	}
	
	/**
	 * Inserts {@code term} into the appropriate bin, {@code knownVar} if size==1, {@code terms} otherwise.
	 * @param term the term to be added
	 * @param terms the terms - term added here if size > 1
	 * @param knownVar the known variables - terms added here if size == 1
	 * @return true if some modification was made
	 */
	private static boolean inject(
		@Unmodified Set<Integer> term,
		@Modified SortedSet<SortedSet<Integer>> terms,
		@Modified Set<Integer> knownVar) {
		return term.size() == 1 ? knownVar.addAll(term) : terms.add(Sets.newTreeSet(term));
	}
	
	/**
	 * The resulting {@link Function} provides a view of the input terms.  If there are no knowns, the function
	 * only adds to {@code knownRBar}.  Otherwise, the view is of the {@link Sets#difference(Set, Set)}
	 * subtracting {@code knownGBar}.
	 * <p>
	 * Conflicting states, such as an input term overlapping with {@code knownR} or being a subset of {@code knownGBar}
	 * are noted in {@code conflicts}.
	 * @param knownR the known inhibiting edge sources
	 * @param knownGBar the known non-activating edge sources
	 * @param knownRBar the known non-inhibiting edge sources - added to by applications of the function
	 * @param conflicts any conflicts between knowns and term - added to by applications of the function
	 * @return a function that turns on states into gterms
	 */
	private static Function<Set<Integer>,Set<Integer>> gTermTransform(
		@Unmodified	final Set<Integer> knownR, 
		@Unmodified	final Set<Integer> knownGBar,
		@Modified	final Set<Integer> knownRBar,
		@Modified	final SetMultimap<Edge,Integer> conflicts) {
		return !knownR.isEmpty() || !knownGBar.isEmpty() ? 
		new Function<Set<Integer>,Set<Integer>>() {
			@Override public Set<Integer> apply(final Set<Integer> term) {
				if (!Collections.disjoint(term, knownR)) conflicts.putAll(TURN_OFF, intersection(term,knownR));
				Set<Integer> diff = difference(term, knownGBar);
				knownRBar.addAll(term);
				if (diff.isEmpty()) conflicts.putAll(NOT_TURN_ON, intersection(knownGBar,term));
				return diff;
			} } :
		new Function<Set<Integer>,Set<Integer>>() {
			@Override public Set<Integer> apply(final Set<Integer> term) {
				knownRBar.addAll(term);
				return term;
			} } ;
	}
	
	public static final Function<Set<Integer>,SortedSet<Integer>> sortedDiff(final Set<Integer> remove) {
		return new Function<Set<Integer>,SortedSet<Integer>>() {
			@Override public SortedSet<Integer> apply(Set<Integer> term) {
				return Sets.newTreeSet(difference(term,remove));
			}
		};
	}
	
	public static final Function<Set<Integer>,ImmutableSortedSet<Integer>> immutableSortedDiff(final Set<Integer> remove) {
		return new Function<Set<Integer>,ImmutableSortedSet<Integer>>() {
			@Override public ImmutableSortedSet<Integer> apply(Set<Integer> term) {
				return ImmutableSortedSet.copyOf(difference(term,remove));
			}
		};
	}

	/**
	 * Sugar wrapper method for
	 * {@link #processOnPrecursors(Set, Set, Set, Set, SortedSet, Iterable)}.
	 */
	public static SetMultimap<Edge,Integer> processOnPrecursors(
			@Unmodified final Set<Integer> knownR, 
			@Unmodified final Set<Integer> knownGBar,
			@Modified	final Set<Integer> knownRBar,
			@Modified	final Set<Integer> knownG,
			@Modified	final SortedSet<SortedSet<Integer>> gTerms,
			@Unmodified	final Set<Integer> onPrecursors)
	{ return processOnPrecursors(knownR,knownGBar,knownRBar,knownG,gTerms,ImmutableSet.of(onPrecursors)); }

	/**
	 * Splits a set of on vertices into possible inhibitors and interfering activators.
	 * @param knownRBar known non-inhibiting edge sources
	 * @param knownGBar known non-activating edge sources - added to on function calls
	 * @return the function
	 */
	private static Function<Set<Integer>,Entry<SortedSet<Integer>,Set<Integer>>> rTermsTransformer(
		@Unmodified final Set<Integer> knownRBar,
		@Modified	final Set<Integer> knownGBar) {
		return new Function<Set<Integer>,Entry<SortedSet<Integer>,Set<Integer>>>(){
			@Override public Entry<SortedSet<Integer>, Set<Integer>> apply(Set<Integer> from) {
				sortedDiff(knownRBar).apply(from);
				rTermEntry processed =  new rTermEntry(
					ImmutableSortedSet.copyOf(difference(from,knownRBar)),
					Sets.newHashSet(from)
				);
				if (processed.getKey().size() < 2) knownGBar.addAll(processed.getKey().isEmpty() ? processed.getValue() : processed.getKey());
				return processed;
			}
		};
	}
	
	private static void injectRTerm(SortedSetMultimap<SortedSet<Integer>,Integer> rTerms, Entry<SortedSet<Integer>,Set<Integer>> term) {
		injectRTerm(rTerms, term.getKey(), term.getValue());
	}
	
	private static void injectRTerm(
		SortedSetMultimap<SortedSet<Integer>,Integer> rTerms,
		SortedSet<Integer> rTerm,
		Set<Integer> gNegTerm) {
		
		if (rTerm.isEmpty()) return;
		
		rTerms.putAll(rTerm,gNegTerm);
	}
	
	private static class rTermEntry implements Entry<SortedSet<Integer>, Set<Integer>> {
		rTermEntry(SortedSet<Integer> r, Set<Integer> notG) { rTerm = r; gNegTerm = notG; }
		private final SortedSet<Integer> rTerm;
		@Override public SortedSet<Integer> getKey() { return rTerm; }		
		private final Set<Integer> gNegTerm;
		@Override public Set<Integer> getValue() { return gNegTerm; }
		@Override public Set<Integer> setValue(Set<Integer> value) { throw new UnsupportedOperationException(); }
	}
	
	/**
	 * Processes the offPrecursors to finalize knownGBar.
	 * @param offPrecursors sets of on vertices
	 * @param knownR known inhibiting edge sources - only used to bypass terms
	 * @param knownGBar known non-activating edge sources - added to by this method
	 * @param knownRBar known non-inhibiting edge sources
	 * @param knownG known activating edge sources - only used to test for conflicts
	 * @param rTerms the collection of r + gNeg pairings
	 * @return any conflicting edges
	 */
	public static SetMultimap<Edge,Integer> processOffPrecursors(
			@Unmodified	final Set<Integer> knownR,
			@Modified	final Set<Integer> knownGBar,
			@Unmodified final Set<Integer> knownRBar,
			@Unmodified final Set<Integer> knownG,
//			@Modified	final SortedMap<SortedSet<Integer>, Set<Integer>> rTerms,
			@Modified	final SortedSetMultimap<SortedSet<Integer>,Integer> rTerms,
			@Unmodified final Iterable<? extends Set<Integer>> offPrecursors)
	{
		SetMultimap<Edge,Integer> conflicts = HashMultimap.create();
		
		for (Entry<SortedSet<Integer>,Set<Integer>> entry : 
			transform(filter(offPrecursors,evaluateTermFurther(knownR,knownGBar)), rTermsTransformer(knownRBar,knownGBar))) {
			injectRTerm(rTerms,entry);
		}
		
		if (!disjoint(knownG,knownGBar)) conflicts.putAll(NOT_TURN_ON, intersection(knownG,knownGBar));
		
		rTerms.values().removeAll(knownGBar);
				
		return conflicts;
	}
	
	/**
	 * Sugar wrapper method for
	 * {@link #processOffPrecursors(Set, Set, Set, Set, SortedMap, SortedSet, Iterable)}.
	 */
	public static SetMultimap<Edge,Integer> processOffPrecursors(
			@Unmodified	final Set<Integer> knownR,
			@Modified	final Set<Integer> knownGBar,
			@Unmodified final Set<Integer> knownRBar,
			@Unmodified final Set<Integer> knownG,
			@Modified	final SortedSetMultimap<SortedSet<Integer>,Integer> rTerms,
			@Unmodified final Set<Integer> offPrecursors)
	{
		return processOffPrecursors(knownR, knownGBar, knownRBar, knownG, rTerms, ImmutableSet.of(offPrecursors));
	}

	/**
	 * Provide a predicate for whether or not a term needs further evaluation
	 * @param knownR
	 * @param knownGBar
	 * @return p(input) == !input.isEmpty() && disjoint(input,knownR) && !knownGBar.containsAll(input)
	 */
	public static Predicate<Set<Integer>> evaluateTermFurther(
			@Unmodified final Set<Integer> knownR,
			@Unmodified final Set<Integer> knownGBar) {
		return new Predicate<Set<Integer>>() {
			@Override public boolean apply(Set<Integer> input) {
				//TODO possible to join iteration in disjoint/containsAll
				return !input.isEmpty() && disjoint(input,knownR) && !knownGBar.containsAll(input);
			}			
		};
	}

	/**
	 * 
	 * @param gTerms
	 * @param knownGBar
	 * @param knownG
	 * @return
	 */
	public static SetMultimap<Edge,Integer> finalizeOnPrecursors(
		@Modified	final SortedSet<SortedSet<Integer>> gTerms,
		@Unmodified final Set<Integer> knownGBar, 
		@Modified 	final Set<Integer> knownG)
	{
		final SetMultimap<Edge, Integer> conflicts = HashMultimap.create();
		
		if (!gTerms.isEmpty()) conflicts.putAll(subtractBar(gTerms,knownGBar,knownG,NOT_TURN_ON));
		
		return conflicts;
	}
	
	/**
	 * Removes {@code knownBar} from each {@code terms}.  If an item in {@code terms} goes to size == 1,
	 * it is transfered to {@code knownVar}.
	 * <p>
	 * If a term is emptied, it put in the resulting conflicts by {@link Edge} {@code type}.
	 * @param terms
	 * @param knownBar
	 * @param knownVar
	 * @param type
	 * @return
	 */
	public static SetMultimap<Edge,Integer> subtractBar(
		@Modified	final SortedSet<SortedSet<Integer>> terms,
		@Unmodified final Set<Integer> knownBar, 
		@Modified 	final Set<Integer> knownVar,
		@Unmodified final Edge type)
	{
		final SetMultimap<Edge, Integer> conflicts = HashMultimap.create();

		final SortedSet<SortedSet<Integer>> copyterms = Sets.newTreeSet(terms.comparator());
		final Iterator<SortedSet<Integer>> iter = terms.iterator();
		while (iter.hasNext()) {
			SortedSet<Integer> term = iter.next();
			if (!disjoint(term,knownBar)) {
				iter.remove();
				SortedSet<Integer> copy = Sets.newTreeSet(Sets.difference(term, knownBar));
				if (copy.isEmpty()) {
					conflicts.putAll(type, intersection(term,knownBar));
				} else if (copy.size() == 1) {
					knownVar.addAll(copy);
				} else copyterms.add(copy);
			}
		}
		
		terms.addAll(copyterms);
		reduceTerms(terms,knownVar);
		
		return conflicts;
	}

	/**
	 * 
	 * @param rTerms
	 * @param knownR
	 * @param justR
	 * @param gFalse
	 * @return
	 */
	static SetMultimap<Edge,Integer> finalizeOffPrecursors(
//		@Modified	final SortedMap<SortedSet<Integer>, Set<Integer>> rTerms,
		@Modified	final TreeMultimap<SortedSet<Integer>, Integer> rTerms,
		@Modified	final Set<Integer> knownR,
		@Modified	final SortedSet<SortedSet<Integer>> justR,
		@Unmodified final Predicate<Set<Integer>> gFalse)
	{
		final SetMultimap<Edge,Integer> conflicts = HashMultimap.create();
		final Predicate<Set<Integer>> rTrue = termPredicate(knownR,justR);
		Iterator<SortedSet<Integer>> rIter = rTerms.keySet().iterator();
		// N.B. - the keys are sorted by size; later keys cannot displace earlier identified justR terms
		while (rIter.hasNext()) {
			final SortedSet<Integer> test = rIter.next();
			
			if( rTrue.apply(test) ) {
				rIter.remove();
			} else if ( gFalse.apply(rTerms.get(test)) ) { //if it wasn't knocked out, and the g prod is guaranteed false
				if (test.isEmpty()) conflicts.putAll(TURN_ON, rTerms.get(test));
				rIter.remove();
				if (!test.isEmpty()) inject(test,justR,knownR);
			}
			
		}
		
		reduceTerms(justR,knownR);
		
		reduceRTerms(rTerms);
		
		return conflicts;
	}
		
	static void reduceRTerms(TreeMultimap<SortedSet<Integer>,Integer> rTerms) {
		
		for (SortedSet<Integer> subset : ImmutableList.copyOf(rTerms.keySet())) if (rTerms.containsKey(subset)) {
			Set<Integer> gNeg = rTerms.get(subset);//make modifications here?
			Iterator<SortedSet<Integer>> keyIter = rTerms.keySet().tailSet(SmallestFirst.markerSet(subset.size())).iterator();
			while (keyIter.hasNext()) {
				SortedSet<Integer> superset = keyIter.next();
				if (superset.containsAll(subset)) {
					if (gNeg.containsAll(rTerms.get(superset)) ) keyIter.remove();
					else rTerms.get(superset).removeAll(gNeg);
				}
			}
			
			if (gNeg.size() == 1 && subset.containsAll(gNeg)) {
				rTerms.putAll(ImmutableSortedSet.copyOf(difference(subset,gNeg)), gNeg);
				gNeg.clear();
			}
			
		}

	}
			
	public static int estimateMinimumSize(InvertVertex iv) {
		if (iv == null || !iv.isFeasible()) return -1;
		int estimatedMinimum = iv.fixedComponent.get(TURN_ON).size() + iv.fixedComponent.get(TURN_OFF).size();

		final Set<Integer> minGGuess = Sets.newHashSetWithExpectedSize(iv.gTerms.size());
		final Predicate<Collection<Integer>> hasNoPickedG = Predicates.disjoint(minGGuess);

		Iterator<SortedSet<Integer>> termIter = Iterators.filter(iv.gTerms.iterator(), hasNoPickedG);
		Multiset<Integer> counter = HashMultiset.create();
		List<Integer> maxVertex = Lists.newArrayList();

		while (termIter.hasNext()) {
			counter.clear();
			while (termIter.hasNext()) {
				counter.addAll(termIter.next());
			}
			int count = 0;
			for (Integer vertex : counter.elementSet()) {
				if (counter.count(vertex) > count) {
					maxVertex.clear();
					maxVertex.add(vertex);
					count = counter.count(vertex);
				} else if (counter.count(vertex) == count) {
					maxVertex.add(vertex);
				}
			}
			if (maxVertex.size() == 1) {
				minGGuess.addAll(maxVertex);
			} else {
				count = iv.rTerms.size();
				List<Integer> minConflicts = Lists.newArrayListWithExpectedSize(maxVertex.size());
				for (Integer vertex : maxVertex) {
					int myCount = 0;
					//TODO save some steps by testing against count?
					for (Collection<Integer> gNeg : Iterables.filter(iv.rTerms.asMap().values(),hasNoPickedG)) if (gNeg.contains(vertex)) myCount++;
					if (myCount < count) {
						minConflicts.clear();
						minConflicts.add(vertex);
						count = myCount;
					} else if (myCount == count) {
						minConflicts.add(vertex);
					}
				}
				if (minConflicts.size() == 1) {
					minGGuess.addAll(minConflicts);
				} else {
					Collections.shuffle(minConflicts);
					minGGuess.add(minConflicts.get(0));
				}
			}
			termIter = Iterators.filter(iv.gTerms.iterator(), hasNoPickedG);
		}

		final Set<Integer> minRGuess = Sets.newHashSetWithExpectedSize(iv.justR.size()+iv.rTerms.size());		
		Predicate<Collection<Integer>> hasNoPickedR = Predicates.disjoint(minRGuess);

		termIter = filter(concat(iv.justR,Maps.filterValues(iv.rTerms.asMap(), not(hasNoPickedG)).keySet()),hasNoPickedR).iterator();
		while (termIter.hasNext()) {
			counter.clear();
			while (termIter.hasNext()) {
				counter.addAll(termIter.next());
			}
			int count = 0;
			for (Integer vertex : counter.elementSet()) {
				if (counter.count(vertex) > count) {
					maxVertex.clear();
					maxVertex.add(vertex);
					count = counter.count(vertex);
				} else if (counter.count(vertex) == count) {
					maxVertex.add(vertex);
				}
			}
			if (maxVertex.size() == 1) {
				minRGuess.addAll(maxVertex);
			} else {
				Collections.shuffle(maxVertex);
				minRGuess.add(maxVertex.get(0));
			}
			termIter = filter(concat(iv.justR,Maps.filterValues(iv.rTerms.asMap(), not(hasNoPickedG)).keySet()),hasNoPickedR).iterator();
		}
	
		estimatedMinimum += minGGuess.size() + minRGuess.size();
		return estimatedMinimum;
	}
	
	public static int minimumSize(InvertVertex iv) {
		int minimumSize = iv.fixedComponent.get(TURN_ON).size() + iv.fixedComponent.get(TURN_OFF).size();
		if (!iv .minimalEnumeratedComponents()
				.isEmpty()) minimumSize+=iv.minimalEnumeratedComponents().first().size();
		return minimumSize;
	}

	
	public static int minimumSizeNonAuto(InvertVertex iv) {
		int minimumSize = minimumSize(iv);

		if (iv.fixedComponent.get(NOT_TURN_ON).contains(iv.vertex)) {
			minimumSize++;
		} else if (iv.fixedComponent.get(TURN_ON).contains(iv.vertex)) {
			minimumSize--;
		} else if (!iv.minimalEnumeratedComponents().isEmpty()) {
			int reference_size = iv.minimalEnumeratedComponents().first().size();
			for (FlexibleComponent solution : 
			iv.minimalEnumeratedComponents()
			) {

				if (solution.get(TURN_ON).contains(iv.vertex)) {
					minimumSize-=(2-solution.size()+reference_size);
					break;
				}
			}
			minimumSize++;
		};
		
		return minimumSize;
	}
	
}
